Party Lamps

Posted on | Edited on | In | Views:

Party Lamps

Desciption

在IOI98的节日宴会上，我们有$N(10<=N<=100)$盏彩色灯，他们分别从1到N被标上号码。 这些灯都连接到四个按钮：

按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。

按钮2：当按下此按钮，将改变所有奇数号的灯。

按钮3：当按下此按钮，将改变所有偶数号的灯。

按钮4：当按下此按钮，将改变所有序号是$3*K+1(K>=0)$的灯。例如：$1,4,7…$

一个计数器C记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器C为0。

你将得到计数器$C(0<=C<=10000)$上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。

Format

Input

不会有灯会在输入中出现两次。
第一行: N。
第二行: C最后显示的数值。
第三行: 最后亮着的灯,用一个空格分开，以-1为结束。
第四行: 最后关着的灯,用一个空格分开，以-1为结束。

Output

每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符，第1个字符表示1号灯，最后一个字符表示N号灯。0表示关闭，1表示亮着。这些行必须从小到大排列（看作是二进制数）。

如果没有可能的状态，则输出一行’IMPOSSIBLE’。

Example

Input

1
2
3
4
10
1
-1
7 -1

Output

1
2
3
0000000000
0101010101
0110110110

Analyse

这道题可以发现一个操作如果操作了两次就相当于没有操作，所以第一个方法出现了！枚举此操作是否生效，并排除掉不能满足总按键次数的方法就AC了。

（并没有代码）

复杂度虽然满足题目要求了，但是我们还可以继续尝试优化对吧，毕竟题目都是在魔改中变得变态的。
因为只有两个两个和三个三个的操作，那我们就可以把每六个看成一个整体，将序列拆成很多长度为六的序列，特判一下就可以在$O(n)$的时间内干翻这道题了（章口就莱）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define RI register int

using namespace std;

int n, c, a, t1, t2, p, co, open[105], clse[105];

int sit[9][8] = {
    {0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 1, 1, 0},
    {0, 0, 1, 0, 1, 0, 1},
    {0, 0, 1, 1, 0, 1, 1},
    {1, 1, 0, 0, 1, 0, 0},
    {1, 1, 0, 1, 0, 1, 0},
    {1, 1, 1, 0, 0, 0, 1},
    {1, 1, 1, 1, 1, 1, 1}
};

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> c;
    while ("tuliweiAKIOI") {
        cin >> a;
        if (a != -1) open[++t1] = a;
        else break;
    }
    while ("tuliweiAKIOI") {
        cin >> a;
        if (a != -1) clse[++t2] = a;
        else break;
    }
    if(!c) {
    	if (t2) cout << "IMPOSSIBLE";
        else for (RI i = 1; i <= n; ++i) cout << '1';
        cout << '\n';
        return 0;
    }
    for (RI i = 1; i <= 8; ++i) {
        for (RI j = 1; j <= t1; ++j)
            if (!sit[i][(open[j] - 1) % 6 + 1]) p = 1;
        for (RI j = 1; j <= t2; ++j)
            if (sit[i][(clse[j] - 1) % 6 + 1]) p = 1;
        if (!p) {
        	if (c == 1 && (i == 2 || i == 5 || i == 7)) goto A;
            for (RI j = 1; j <= n; ++j) cout << sit[i][(j - 1) % 6 + 1];
            cout << '\n', co = 1;
            A:;
        }
        else p = 0;
    }
    if (!co) cout << "IMPOSSIBLE\n";
}
完结撒花！
Helping poor children in CSSYZ!!!